package com.algorithm;

/**
 * 不同路径
 */
public class UniquePaths {

    public static int uniquePaths(int m, int n) {
        int [][] nums=new int [m][n];
        //第一列补为1
        for (int i = 0; i <= m-1; i++) {
            nums[i][0]=1;
        }
        //第一行补为1
        for (int i = 0; i <= n-1; i++) {
            nums[0][i]=1;
        }
        //补充其他
        for (int i=1;i<=m-1;i++){
            for (int j=1;j<=n-1;j++){
                nums[i][j]=nums[i-1][j]+nums[i][j-1];
            }
        }
        return nums[m-1][n-1];
    }

    public static void main(String[] args) {
        int n = uniquePaths(3, 7);
        System.out.println(n);
    }
}
